package sort;

import java.util.Arrays;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/11/6 14:30
 */
public class SelectSort {
    /**
     * 选择排序：
     *
     * 时间复杂度：
     * 最好/平均/最坏：O(n^2)
     *
     * 空间复杂度：
     * 最好/平均/最坏：O(1)
     *
     * 稳定性：保证不了稳定性
     * @param array
     */
    public static void selectSortAnother(long[] array){
        for (int i = 0; i < array.length-1; i++) { //一共进行n-1次选择
            //  [有序区间][无序区间]
            // 有序区间: [0, i)
            // 无序区间: [i, array.length )

            // 1. 遍历整个无序区间，找到最小的元素所在的下标（不需要知道最大的元素是多少，而是它在哪）

            // 在剩余位置，继续找比 array[maxIdx] 元素还大的元素
            int minIndex = i;
            for (int j = i; j < array.length; j++) {
                // 期间，如果出现更的元素，则更新最大元素所在下标
                if (array[j]<array[minIndex]){
                    minIndex=j;
                }
            }
            // 最大的元素在 [maxIdx]，即 array[maxIdx] 是无序区间的最大元素
            // 把最大的元素放到无序区间的最后一个位置
            // [0, array.length - i)
            // 无序区间的最后一个位置下标是 [array.length - i - 1]
            swap(array,minIndex,i);
        }
    }
    public static void selectSort(long[] array){
        for (int i = 0; i < array.length-1; i++) { //一共进行n-1次选择
            // [无序区间] [有序区间]
            // 无序区间: [0, array.length - i)
            // 有序区间: [array.length - i, array.length)

            // 1. 遍历整个无序区间，找到最大的元素所在的下标（不需要知道最大的元素是多少，而是它在哪）

            // 在剩余位置，继续找比 array[maxIdx] 元素还大的元素
            int maxIndex = 0;
            for (int j = 1; j < array.length-i; j++) {
                // 期间，如果出现更的元素，则更新最大元素所在下标
                if (array[j]>array[maxIndex]){
                    maxIndex=j;
                }
            }
            // 最大的元素在 [maxIdx]，即 array[maxIdx] 是无序区间的最大元素
            // 把最大的元素放到无序区间的最后一个位置
            // [0, array.length - i)
            // 无序区间的最后一个位置下标是 [array.length - i - 1]
            swap(array,maxIndex,array.length-i-1);
        }
    }
    public static void swap(long[] array, int i, int j) {
        long t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
    public static void main(String[] args) {
        long[] array = { 6, 1, 3, 5, 2, 8, 9, 4, 0, 7 };

        selectSortAnother(array);

        System.out.println(Arrays.toString(array));
    }
    // 无序区间: [from, to)
    public static void selectSort递归版本(long[] array, int from, int to) {
        // [无序][有序]
        int size = to - from;
        if (size <= 1) {
            return;
        }

        int maxIdx = from;
        for (int i = from + 1; i < to; i++) {
            if (array[i] > array[maxIdx]) {
                maxIdx = i;
            }
        }

        swap(array, maxIdx, to - 1);

        // 无序区间: [from, to - 1)
        selectSort递归版本(array, from, to - 1);
    }
}
